package com.summli.basic.class06;

import java.util.ArrayList;

/**
 * 快慢指针的问题，
 * 链表的问题主要是在coding，笔试的时候可以不考虑空间复杂度，面试的时候，保障时间复杂的前提下，尽量使用最少的空间
 * 1）输入链表头节点，奇数长度返回中点，偶数长度返回上中点
 *
 * 2）输入链表头节点，奇数长度返回中点，偶数长度返回下中点
 *
 * 3）输入链表头节点，奇数长度返回中点前一个，偶数长度返回上中点前一个
 *
 * 4）输入链表头节点，奇数长度返回中点前一个，偶数长度返回下中点前一个
 */
public class Code01_LinkedListMid {
    public static class Node {
        public int value;
        public Node next;

        public Node(int v) {
            value = v;
        }
    }

    // 问题1：奇数长度返回中点，偶数长度返回上中点
    public static Node midOrUpMidNode(Node node){
        if(node ==null || node.next ==null || node.next.next == null){
            return node;
        }
        //node长度>=3
        Node last = node;
        Node fast = node;
        while(fast.next != null && fast.next.next != null){
            last = last.next;
            fast = fast.next.next;
        }
        return last;
    }

    // 问题2：奇数长度返回中点，偶数长度返回下中点
    public static Node midOrDownMidNode(Node node){
        if(node ==null || node.next ==null){
            return node;
        }
        Node last = node.next;
        Node fast = node.next;
        while(fast.next != null && fast.next.next != null){
            last = last.next;
            fast = fast.next.next;
        }
        return last;
    }

    // 问题3：奇数长度返回中点前一个，偶数长度返回上中点前一个
    public static Node midOrUpMidPreNode(Node node){
        if(node == null || node.next == null || node.next.next == null){
            return node;
        }
        Node last = node;
        Node fast = node.next.next;
        while(fast.next != null && fast.next.next != null){
            last = last.next;
            fast = fast.next.next;
        }
        return last;
    }

    // 奇数长度返回中点前一个，偶数长度返回下中点前一个
    public static Node midOrDownMidPreNode(Node node){
        if(node == null || node.next == null){
            return node;
        }
        Node last = node;
        Node fast = node.next;
        while(fast.next != null && fast.next.next != null){
            last = last.next;
            fast = fast.next.next;
        }
        return last;
    }

    public static Node right1(Node head) {
        if(head == null){
            return head;
        }
        Node cur = head;
        ArrayList<Node> arr = new ArrayList<>();
        while(cur !=null){
            arr.add(cur);
            cur = cur.next;
        }
        return arr.get((arr.size()-1)/2);
    }

    public static Node right2(Node head) {
        if(head == null){
            return head;
        }
        Node cur = head;
        ArrayList<Node> arr = new ArrayList<>();
        while(cur !=null){
            arr.add(cur);
            cur = cur.next;
        }
        return arr.get(arr.size()/2);
    }

    public static Node right3(Node head) {
        if (head == null || head.next == null || head.next.next == null) {
            return null;
        }
        Node cur = head;
        ArrayList<Node> arr = new ArrayList<>();
        while(cur !=null){
            arr.add(cur);
            cur = cur.next;
        }
        return arr.get((arr.size()-3)/2);
    }

    public static Node right4(Node head) {
        if (head == null || head.next == null) {
            return null;
        }
        Node cur = head;
        ArrayList<Node> arr = new ArrayList<>();
        while(cur !=null){
            arr.add(cur);
            cur = cur.next;
        }
        return arr.get((arr.size()-2)/2);
    }

    public static void main(String[] args) {
        Node test = null;
        test = new Node(0);
        test.next = new Node(1);
        test.next.next = new Node(2);
        test.next.next.next = new Node(3);
        test.next.next.next.next = new Node(4);
        test.next.next.next.next.next = new Node(5);
        test.next.next.next.next.next.next = new Node(6);
        test.next.next.next.next.next.next.next = new Node(7);
        //test.next.next.next.next.next.next.next.next = new Node(8);

        Node ans1 = null;
        Node ans2 = null;

        ans1 = midOrUpMidNode(test);
        ans2 = right1(test);
        System.out.println(ans1 != null ? ans1.value : "无");
        System.out.println(ans2 != null ? ans2.value : "无");

        System.out.println("++++++++++++++++++++++++++++++++++");

        ans1 = midOrDownMidNode(test);
        ans2 = right2(test);
        System.out.println(ans1 != null ? ans1.value : "无");
        System.out.println(ans2 != null ? ans2.value : "无");
        System.out.println("++++++++++++++++++++++++++++++++++");
        ans1 = midOrUpMidPreNode(test);
        ans2 = right3(test);
        System.out.println(ans1 != null ? ans1.value : "无");
        System.out.println(ans2 != null ? ans2.value : "无");
        System.out.println("++++++++++++++++++++++++++++++++++");
        ans1 = midOrDownMidPreNode(test);
        ans2 = right4(test);
        System.out.println(ans1 != null ? ans1.value : "无");
        System.out.println(ans2 != null ? ans2.value : "无");

    }
}
